package sorting;

import util.ArrayUtil;
import util.MathUtil;
import util.Tracer;

public class JugGrouping {

	public static void group1(Jug[] redJugs, Jug[] blueJugs)
	{
		for(int i = 0, redLength = redJugs.length; i < redLength; i ++)
		{
			for(int j = 0, blueLength = blueJugs.length; j < blueLength; j ++)
			{
				if(redJugs[i].getCapacity() == blueJugs[j].getCapacity())
				{
					Tracer.trace(redJugs[i], blueJugs[j]);
					break;
				}
			}
		}
	}
		
	public static void group2(Jug[] redJugs, Jug[] blueJugs)
	{
		group2(redJugs, blueJugs, 0, redJugs.length - 1);
	}
	public static void group2(Jug[] redJugs, Jug[] blueJugs, int from, int to)
	{
		if(from == to)
		{
			Tracer.trace(redJugs[to], blueJugs[to]);
			return;
		}
		
		if(to > from + 1)
			ArrayUtil.each(redJugs, to, MathUtil.random(from, to));

		int part = partition(redJugs, blueJugs, from, to);
		if(part > from)
			group2(redJugs, blueJugs, from, part - 1);
		
		if(to > part)
			group2(redJugs, blueJugs, part + 1, to);
	}

	public static int partition(Jug[] redJugs, Jug[] blueJugs, int from, int to)
	{
		Jug redPivot = redJugs[to];
		Jug bluePivot = null;
		int bluePivotIndex = 0;

		int part = from;
		for(int i = from; i <= to; i ++)
		{
			Jug blueJug = blueJugs[i];
			if(blueJug.getCapacity() <= redPivot.getCapacity())
			{
				ArrayUtil.each(blueJugs, i, part);
				
				if(blueJug.getCapacity() == redPivot.getCapacity())
				{
					bluePivotIndex = part;
					bluePivot = blueJug;
					Tracer.trace(redPivot, bluePivot);
				}
				
				++ part;
			}
		}

		ArrayUtil.each(blueJugs, bluePivotIndex, part - 1);

		part = from;
		for(int i = from; i < to; i ++)
		{
			if(redJugs[i].getCapacity() < bluePivot.getCapacity())
			{
				ArrayUtil.each(redJugs, i, part ++);
			}
		}
		
		ArrayUtil.each(redJugs, to, part);

		return part;
	}
	
	public static void main(String[] args) {
		Jug[] redJugs = new Jug[]{
				new Jug(0, 5, JugColor.RED),
				new Jug(1, 3, JugColor.RED),
				new Jug(2, 4, JugColor.RED),
				new Jug(3, 2, JugColor.RED),
				new Jug(4, 1, JugColor.RED)
		};
		
		Jug[] blueJugs = new Jug[]{
				new Jug(0, 4, JugColor.BLUE),
				new Jug(1, 2, JugColor.BLUE),
				new Jug(2, 5, JugColor.BLUE),
				new Jug(3, 1, JugColor.BLUE),
				new Jug(4, 3, JugColor.BLUE)
		};
		
		group2(redJugs, blueJugs);
	}
}


class Jug
{
	public Jug(int index, int capacity, JugColor color) {
		setIndex(index);
		setCapacity(capacity);
		setColor(color);
	}
	
	private int capacity;
	private int index;
	private JugColor color;
	public int getCapacity() {
		return capacity;
	}
	public void setCapacity(int capacity) {
		this.capacity = capacity;
	}
	public JugColor getColor() {
		return color;
	}
	public void setColor(JugColor color) {
		this.color = color;
	}
	public int getIndex() {
		return index;
	}
	public void setIndex(int index) {
		this.index = index;
	}
	
	@Override
	public String toString() {
		return "{" + color + "," + capacity + "}";
	}
}

enum JugColor
{
	RED,BLUE
}